/// @tags:
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

int constexpr N = 100;

int a[N], buk[N], fac[N], ifac[N];
vector<int> vec;

inline LL qpow(LL base, int exp, int P) {
  LL res = 1;
  for (; exp; exp >>= 1, base = base * base % P)
    if (exp & 1) res = res * base % P;
  return res;
}

inline LL C(int n, int m, int P) { return (LL)fac[n] * ifac[n - m] % P * ifac[m] % P; }

inline int inc(int a, int b, int P) {
  a += b;
  return a >= P ? a - P : a;
}

inline int main() {
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int l, r, P; q; --q) {
    cin >> l >> r >> P;
    int ans = 0;
    for (int i = l; i <= r; ++i) {
      vec.push_back(a[i]);
      buk[a[i]]++;
    }
    for (int i = 1, ilim = r - l + 1; i <= ilim; ++i) fac[i] = (LL)fac[i - 1] * i % P;
    // ifac[r - l + 1] = qpow(fac[r - l + 1], P - 2);
    for (auto i : vec) {
      for (int j = 1; j <= buk[i]; ++j) {
        ans = inc(ans, i * C(buk[i], j, P) % P * qpow(2, r - l + 1 - buk[i], P) % P, P);
      } 
    }
    cout << ans << '\n';
    for (auto i : vec) buk[i] = 0;
    vec.clear();
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("lorem.in", "r", stdin);
  freopen("lorem.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
